package main.leetcode.primary.from101to200;

/**
 * 153.寻找旋转排序数组中的最小值
 *
 * <p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 *
 * <p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 *
 * <p>请找出其中最小的元素。
 *
 * <p>你可以假设数组中不存在重复元素。
 *
 * <p>示例 1: 输入: [3,4,5,1,2] 输出: 1
 *
 * <p>示例 2: 输入: [4,5,6,7,0,1,2] 输出: 0
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex153 {
    public static void main(String[] args) {
        System.out.println(new ex153().findMin(new int[] {4, 5, 6, 7, 0, 1, 2}));
        System.out.println(new ex153().findMin(new int[] {3, 4, 5, 1, 2}));
        System.out.println(new ex153().findMin(new int[] {2, 3, 4, 5, 1}));
    }

    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while (l < r) {
            if (nums[l] < nums[r]) {
                return nums[l];
            }
            mid = l + ((r - l) >> 1);
            if (nums[mid] < nums[r]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}
